/*
 * file:  expr.cpp (implementation of Expr).
 * Author: Jeremy Johnson 
 * Date: 2/5/07
 *
 * Description: 
 */

#include <iostream>
#include <string>
#include <map>
#include <list>
#include <cstdlib>
#include "programext.h"

using namespace std;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
HeapCell::HeapCell(int _cdr)
{
	mark = false;
	isPtr = false;
	isEmptyList = false;
	car = 0;
	cdr = _cdr;
}

void HeapCell::print()
{
	if(isPtr)
	{
		cout<<"ptr["<<car<<"]";
	}
	else
		cout<<car;
}

Heap::Heap(int size,map<string,Element> *_nameTable)
{
	nameTable = _nameTable;
	
	heapSize = size;
	available = 0;//initially available position is set to zero
	
	for(int i=0;i<heapSize-1;i++)
	{
		cells.push_back(HeapCell(i+1));
	}
	cells.push_back(HeapCell(-1));//denoting nil
}

int Heap::putValue(Element elm,int _cdr)
{
	if(isAvailable()==false)
	{
		cout << "Out of memory" << endl;
		exit(1);
	}	
	int memoryAddr = available;
	
	//keep temp name list for noname lists like: [1,2,3,[ ],5]
	if(_cdr == -1)
		tempNameTablePtr++;//insert a new noname list
	tempNameTable[tempNameTablePtr] = memoryAddr;
	
	updateAvailableCell();
	
	cells[memoryAddr].car = elm.value;
	cells[memoryAddr].cdr = _cdr;
	
	cells[memoryAddr].isPtr = elm.dataType==LIST?true:false;
	
	cells[memoryAddr].mark = true;
	cells[memoryAddr].isEmptyList = false;
	
	return memoryAddr;	
}

int Heap::putEmptyList()
{
	if(isAvailable()==false)
	{
		cout << "Out of memory" << endl;
		exit(1);
	}
	int memoryAddr = available;
	
	//keep temp name list for noname lists like: [1,2,3,[ ],5]
	tempNameTablePtr++;//insert a new noname list
	tempNameTable[tempNameTablePtr] = memoryAddr;
	
	updateAvailableCell();
	
	cells[memoryAddr].car = 0;//garbage
	cells[memoryAddr].cdr = -1;
	
	cells[memoryAddr].isPtr = false;
	
	cells[memoryAddr].mark = true;
	
	cells[memoryAddr].isEmptyList = true;
	
	return memoryAddr;	
}

void Heap::updateAvailableCell()
{
	available = cells[available].cdr;
}

bool Heap::isAvailable()
{
	if(available==-1)//if not available
		markAndSweep();//run mark and sweep algorithm to make garbage collection

	return available==-1?false:true;//if we open up some space, return true, else return false
}

void Heap::markAndSweep()
{
	map<string,Element>::iterator p;
	map<int,int>::iterator q;

	for (p = nameTable->begin();p != nameTable->end();p++)
	{
		if(p->second.dataType==LIST)
			mark(p->second.value);
	}
	for (q = tempNameTable.begin();q != tempNameTable.end();q++)
	{
		mark(q->second);
	}
	
	sweep();	
	unmark();	
}

void Heap::mark(int ptr)
{
	cells[ptr].mark = true;
	if(cells[ptr].isPtr==true)
		mark(cells[ptr].car);
	
	if(cells[ptr].cdr != -1)
		mark(cells[ptr].cdr);
}
void Heap::unmark()
{
	for(int i=0;i<heapSize;i++)
	{
		cells[i].mark = false;
	}
}
void Heap::sweep()
{
	for(int i=0;i<heapSize;i++)
	{
		if(cells[i].mark == false)
		{
			cells[i].car = 0;
			cells[i].cdr = available;
			
			cells[i].isPtr = false;			
			cells[i].isEmptyList = false;
			
			available = i;
		}
	}
}

void Heap::print()
{
	cout<<"Heap Car";
	cout<<"[";
	for(int i=0;i<heapSize-1;i++)
	{
		cells[i].print();
		cout<<",";
	}
	cells[heapSize-1].print();
	cout<<"]"<<endl;
	
	cout<<"Heap Cdr";
	cout<<"[";
	for(int i=0;i<heapSize-1;i++)
	{
		cout<<cells[i].cdr<<",";
	}
	cout<<cells[heapSize-1].cdr<<"]"<<endl;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Element List::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	heap->tempNameTablePtr = 0;
	heap->tempNameTable.clear();
	
	Element *elm = new Element(sequence->eval(NT,FT,heap).value,LIST);
	
	heap->tempNameTable.clear();	
	heap->unmark();
	return *elm;
}
//////////element functions
Element::Element(int _value, int _dataType)
{
	value = _value;	
	dataType = _dataType;
}

void Element::update(int _value, int _dataType)
{
	value = _value;	
	dataType = _dataType;
}

void Element::print(Heap *heap)
{//will be updated
	if(dataType==LIST)
	{
		printList(heap,value);
	}
	else
		cout<<value;
}

void Element::printList(Heap *heap, int position)
{
	int ptr=position;
	cout<<"[";
	while(1)
	{
		if(heap->cells[ptr].isEmptyList==true)
			break;
		else if(heap->cells[ptr].isPtr)
		{
			printList(heap,heap->cells[ptr].car);
		}
		else
		{
			cout<<heap->cells[ptr].car;
		}
		if(heap->cells[ptr].cdr==-1)
			break;		
		cout<<",";
		ptr = heap->cells[ptr].cdr;
	}
	cout<<"]";
}

Element& Element::operator=(const Element& elm)
{
	value = elm.value;
	dataType = elm.dataType;
	
	return *this;
}

//////////////////////////
Element Cons::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	int memoryAddress;
	
	if(expr==NULL && lst==NULL)
	{
		memoryAddress = heap->putEmptyList();
	}
	else if(lst == NULL)
	{
		memoryAddress = heap->putValue(expr->eval(NT,FT,heap),-1);
	}
	else
	{
		memoryAddress = heap->putValue(expr->eval(NT,FT,heap),lst->eval(NT,FT,heap).value);
	}
	return Element(memoryAddress,LIST);
}

//List Functions
Element Concatenate::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	Element elm1,elm2;
	int memoryAddress;
	
	elm1 = l1->eval(NT,FT,heap);
	elm2 = l2->eval(NT,FT,heap);
	
	if(elm1.dataType!=LIST || elm2.dataType!=LIST)
	{
		cout<<"Syntax Error: concatenate operator requires second parameter to be a list"<<endl;
		exit(1);
	}
	
	vector<Element> temp;
	int ptr = elm1.value;
	bool type;
	while(1)
	{
		if(ptr == -1)
			break;
		
		if(heap->cells[ptr].isPtr==true)
			type = LIST;
		else
			type = VALUE;
		temp.push_back(Element(heap->cells[ptr].car,type));
		ptr = heap->cells[ptr].cdr;
	}
	memoryAddress =elm2.value;
	for(int i=temp.size()-1;i>=0;i--)
	{
		memoryAddress = heap->putValue(temp[i],memoryAddress);
	}
		
	return Element(memoryAddress,LIST);
}

Element Cdr::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	Element elm;

	elm = expr->eval(NT,FT,heap);
	
	if(elm.dataType!=LIST)
	{
		cout<<"Syntax Error: cdr function takes list as argument"<<endl;
		exit(1);
	}
	else
	{
		if(heap->cells[elm.value].cdr == -1)
			return Element(0,EMPTY_LIST);
		else
			return Element(heap->cells[elm.value].cdr,LIST);
	}
}

Element Car::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	Element elm;

	elm = expr->eval(NT,FT,heap);
	
	if(elm.dataType!=LIST)
	{
		cout<<"Syntax Error: car function takes list as argument"<<endl;
		exit(1);
	}
	else
	{
		if(heap->cells[elm.value].isEmptyList)
			return Element(0,EMPTY_LIST);
		if(heap->cells[elm.value].isPtr)
			return Element(heap->cells[elm.value].car,LIST);
		else
			return Element(heap->cells[elm.value].car,VALUE);
	}
}

Element Nullp::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	Element elm;
	elm = lst->eval(NT,FT,heap);
	
	bool returnVal;
	
	if(elm.dataType!=LIST)
	{
		cout<<"Syntax Error: nullp function takes list as argument"<<endl;
		exit(1);
	}
	else
	{
		returnVal = heap->cells[elm.value].isEmptyList;
	}
	
	return returnVal?Element(1,VALUE):Element(0,VALUE);
}

Element Intp::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	Element elm;
	elm = exp->eval(NT,FT,heap);
	
	if(elm.dataType==VALUE)
		return Element(1,VALUE);
	else
		return Element(0,VALUE);
}
Element Listp::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	Element elm;
	elm = exp->eval(NT,FT,heap);
	
	if(elm.dataType!=VALUE)
		return Element(1,VALUE);
	else
		return Element(0,VALUE);
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Program::Program(StmtList *SL,int _memSize)
{
	NameTable_.clear();
	FunctionTable_.clear();
	SL_ = SL;
	memSize=_memSize;
	buildHeap( &NameTable_);//supply heap size and nameTable as parameter
}

void Program::dump() 
{
  map<string,Element>::iterator p;
  map<string,Proc*>::iterator f;

  cout << "Dump of Symbol Table" << endl;
  cout << "Name Table" << endl;
  for (p = NameTable_.begin();p != NameTable_.end();p++)
  {
    cout << p->first << " -> " ; p->second.print(heap);cout << endl;
  }
  cout << "Function Table" << endl;
  for (f = FunctionTable_.begin();f != FunctionTable_.end();f++) 
    cout << f->first << endl;
}

void Program::eval() 
{
	SL_->eval(NameTable_, FunctionTable_, heap);
}


void StmtList::insert(Stmt * S)
{
  SL_.push_front(S);
}

void StmtList::eval(map<string,Element> &NT, map<string,Proc*> &FT, Heap *heap) 
{
  list<Stmt*>::iterator Sp;
  for (Sp = SL_.begin();Sp != SL_.end();Sp++)
	(*Sp)->eval(NT,FT,heap);
}

AssignStmt::AssignStmt(string name, Expr *E)
{
  name_ = name;
  E_ = E;
}

void AssignStmt::eval(map<string,Element> &NT, map<string,Proc*> &FT, Heap *heap) const
{
	NT[name_] = E_->eval(NT,FT,heap);
}

DefineStmt::~DefineStmt()
{
  delete P_; 
}

DefineStmt::DefineStmt(string name, Proc *P)
{
  name_ = name;
  P_ = P;
}

void DefineStmt::eval(map<string,Element> &NT, map<string,Proc*> &FT, Heap *heap) const
{
	FT[name_] = P_;
}

IfStmt::IfStmt(Expr *E, StmtList *S1, StmtList *S2)
{
  E_ = E;
  S1_ = S1;
  S2_ = S2;
}

IfStmt::~IfStmt() { delete E_; delete S1_; delete S2_; }

void IfStmt::eval(map<string,Element> &NT, map<string,Proc*> &FT, Heap *heap) const
{
	if (E_->eval(NT,FT,heap).value > 0)
		S1_->eval(NT,FT,heap);
	else
		S2_->eval(NT,FT,heap);
}

WhileStmt::WhileStmt(Expr *E, StmtList *S)
{
  E_ = E;
  S_ = S;
}

WhileStmt::~WhileStmt() { delete E_; delete S_; }

void WhileStmt::eval(map<string,Element> &NT, map<string,Proc*> &FT, Heap *heap) const
{
	while (E_->eval(NT,FT,heap).value > 0) 
		S_->eval(NT,FT,heap);
}

Number::Number(int value)
{
	value_ = value;
}

Element Number::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	return Element(value_,VALUE);
}

Ident::Ident(string name)
{
	name_ = name;
}

Element Ident::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	return NT[name_];
}

Plus::Plus(Expr* op1, Expr* op2)
{
	op1_ = op1;
	op2_ = op2;
}

Element Plus::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	return Element(op1_->eval(NT,FT,heap).value + op2_->eval(NT,FT,heap).value,VALUE);
}

Minus::Minus(Expr* op1, Expr* op2)
{
	op1_ = op1;
	op2_ = op2;
}

Element Minus::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	return Element(op1_->eval(NT,FT,heap).value - op2_->eval(NT,FT,heap).value,VALUE);
}

Times::Times(Expr* op1, Expr* op2)
{
	op1_ = op1;
	op2_ = op2;
}

Element Times::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	return Element(op1_->eval(NT,FT,heap).value * op2_->eval(NT,FT,heap).value,VALUE);
}

FunCall::FunCall(string name, list<Expr*> *AL)
{
	name_= name;
	AL_ = AL;
}

FunCall::~FunCall() { delete AL_; }

Element FunCall::eval(map<string,Element> NT, map<string,Proc*> FT, Heap *heap)
{
	return FT[name_]->apply(NT, FT, heap, AL_);
}


Proc::Proc(list<string> *PL, StmtList *SL)
{
	SL_ = SL;
	PL_ = PL;
	NumParam_ = PL->size();
}

Element Proc::apply(map<string,Element> &NT, map<string,Proc*> &FT, Heap *heap, list<Expr*> *EL) 
{
	map<string,Element> NNT;
	NNT.clear();

	// bind parameters in new name table

	list<string>::iterator p;
	list<Expr*>::iterator e;
	if (NumParam_ != EL->size()) {
		cout << "Param count does not match" << endl;
		exit(1);
	}
	for (p = PL_->begin(), e = EL->begin(); p != PL_->end(); p++, e++) 
		NNT[*p] = (*e)->eval(NT,FT,heap);

	// evaluate function body using new name table and old function table

	SL_->eval(NNT,FT,heap);
	if ( NNT.find("return") != NNT.end() )
		return NNT["return"];
	else {
		cout << "Error:  no return value" << endl;
		exit(1);
	}
}
